namespace ds
{

    /**
     * 树状数组
     * 
     * 树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables[1]为题发表在SOFTWARE PRACTICE AND EXPERIENCE。
     * 
     * @see https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/fenwick-tree
     * @see https://en.wikipedia.org/wiki/Fenwick_tree
     * @see https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
     * @see https://www.youtube.com/watch?v=CWDQJGaN1gY&index=18&t=0s&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8
     */
    export class FenwickTree
    {
        arraySize: number;
        treeArray: number[];

        /**
         * 构建树状数组
         * 
         * @param arraySize 数组尺寸
         */
        constructor(arraySize: number)
        {
            this.arraySize = arraySize;

            // 用0填充树数组
            this.treeArray = [];
            for (let i = 0, n = arraySize + 1; i < n; i++)
            {
                this.treeArray[i] = 0;
            }
        }

        /**
         * 增加值到指定位置上
         * 
         * @param position 位置
         * @param value 值
         */
        increase(position: number, value: number)
        {
            if (position < 1 || position > this.arraySize)
            {
                throw new Error('位置超出允许范围');
            }

            for (let i = position; i <= this.arraySize; i += (i & -i))
            {
                this.treeArray[i] += value;
            }

            return this;
        }

        /**
         * 从索引1到位置的查询和。
         * 
         * @param position 位置
         */
        query(position: number)
        {
            if (position < 1 || position > this.arraySize)
            {
                throw new Error('位置超出允许范围');
            }

            let sum = 0;

            for (let i = position; i > 0; i -= (i & -i))
            {
                sum += this.treeArray[i];
            }

            return sum;
        }

        /**
         * 从leftIndex到rightIndex的查询和。
         * 
         * @param leftIndex  起始索引
         * @param rightIndex 结束索引
         */
        queryRange(leftIndex: number, rightIndex: number)
        {
            if (leftIndex > rightIndex)
            {
                throw new Error('leftIndex 不能大于 rightIndex');
            }

            if (leftIndex === 1)
            {
                return this.query(rightIndex);
            }

            return this.query(rightIndex) - this.query(leftIndex - 1);
        }
    }
}